2004

Created at : 2024-02-10 23:33
2004

#include <iostream>
#include <vector>

using namespace std;

uint64_t f(uint64_t n, uint64_t x);

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    uint64_t a[2], b[2], c[2];
    a[0] = f(n, 5);
    a[1] = f(n, 2);
    b[0] = f(m, 5);
    b[1] = f(m, 2);
    c[0] = f(n - m, 5);
    c[1] = f(n - m, 2);
    
    cout << min(a[0] - b[0] - c[0], a[1] - b[1] - c[1]);

    return 0;
}

uint64_t f(uint64_t n, uint64_t x)
{
    int Count = 0;
    for(uint64_t i = x; n / i >= 1; i *= x)
    {
        Count += n / i;
    }
    return Count;
}

원하는 소인수의 갯수를 구하는 방법에 대해 고민해 봐야 하는 문제이다.

유형

수학
정수론